Skip to content

Latest commit

 

History

History

0622-Design Circular Queue

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
README_CN.md
README_CN.md
 
 
Solution.rs
Solution.rs
 
 

README.md

622. Design Circular Queue

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer".

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Your implementation should support following operations:

  • MyCircularQueue(k): Constructor, set the size of the queue to be k.
  • Front: Get the front item from the queue. If the queue is empty, return -1.
  • Rear: Get the last item from the queue. If the queue is empty, return -1.
  • enQueue(value): Insert an element into the circular queue. Return true if the operation is successful.
  • deQueue(): Delete an element from the circular queue. Return true if the operation is successful.
  • isEmpty(): Checks whether the circular queue is empty or not.
  • isFull(): Checks whether the circular queue is full or not.

Example:

MyCircularQueue circularQueue = new MyCircularQueue(3); // set the size to be 3 circularQueue.enQueue(1); // return true circularQueue.enQueue(2); // return true circularQueue.enQueue(3); // return true circularQueue.enQueue(4); // return false, the queue is full circularQueue.Rear(); // return 3 circularQueue.isFull(); // return true circularQueue.deQueue(); // return true circularQueue.enQueue(4); // return true circularQueue.Rear(); // return 4

Note:

  • All values will be in the range of [0, 1000].
  • The number of operations will be in the range of [1, 1000].
  • Please do not use the built-in Queue library.

Solutions (Rust)

1. Solution

structMyCircularQueue{data:Vec<i32>,size:usize,len:usize,head:usize,}/** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */implMyCircularQueue{/** Initialize your data structure here. Set the size of the queue to be k. */fnnew(k:i32) -> Self{let k = k asusize;Self{data:vec![0; k],size: k,len:0,head:0,}}/** Insert an element into the circular queue. Return true if the operation is successful. */fnen_queue(&mutself,value:i32) -> bool{ifself.is_full(){false}else{self.data[(self.head + self.len) % self.size] = value;self.len += 1;true}}/** Delete an element from the circular queue. Return true if the operation is successful. */fnde_queue(&mutself) -> bool{ifself.is_empty(){false}else{self.head += 1;self.head %= self.size;self.len -= 1;true}}/** Get the front item from the queue. */fnfront(&self) -> i32{ifself.is_empty(){ -1}else{self.data[self.head]}}/** Get the last item from the queue. */fnrear(&self) -> i32{ifself.is_empty(){ -1}else{self.data[(self.head + self.len - 1) % self.size]}}/** Checks whether the circular queue is empty or not. */fnis_empty(&self) -> bool{self.len == 0}/** Checks whether the circular queue is full or not. */fnis_full(&self) -> bool{self.len == self.size}}/** * Your MyCircularQueue object will be instantiated and called as such: * let obj = MyCircularQueue::new(k); * let ret_1: bool = obj.en_queue(value); * let ret_2: bool = obj.de_queue(); * let ret_3: i32 = obj.front(); * let ret_4: i32 = obj.rear(); * let ret_5: bool = obj.is_empty(); * let ret_6: bool = obj.is_full(); */
close